I have a user who was promoted to another job. He wanted a clean mailbox for the new job. So we backed up the mailbox and deleted it. Then created a new mailbox. He is using the same AD Account and email addresses. Now when users reply to existing messages or send a message using an entry in their Auto Complete list they get this message: The e-mail account does not exist at the organization this message was sent to. Check the e-mail address, or contact the recipient directly to find out the correct address. <servername #5.1.1> Deleting the entry in the Auto Complete list and re-selecting his name from the GAL fixes the problem for new messages but not existing messages or meeting invitations. Has anyone ever experienced this and found a solution? Is it possible to create a new mailbox for an existing user and avoid this problem? Thank You

Sure. Your mistake was recreating the mailbox :) The legacyExchangeDN was changed when you did that. Outlook has the original value cached. What you need to do is add the old legacyexchangedn as a custom x.500 address to the new mailbox. So, add in the fomat below ( the old legacyexchangedn. You can look at the NDR to see what the old alias was. Compare to existing legacyExchangeDNs) /o=YourOrg/ou=admingGroup/cn=Recipients/cn=originalalias

Thank you so much, Andy. Adding the X500 address fixed this issue.